package com.wujunshen.algorithm.leetcode.basic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/25 12:05<br>
 */
public class 账户合并 {
  public static List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, String> q = new HashMap<>();
    // 这个映射存储每个邮箱对应账户的名字
    Map<String, String> names = new HashMap<>();

    // 遍历所有账户构建并查集
    for (List<String> a : accounts) {
      for (int i = 1; i < a.size(); i++) {
        if (!q.containsKey(a.get(i))) {
          // 如果并查集中没有这个邮箱，则添加邮箱，其根元素就是本身
          q.put(a.get(i), a.get(i));
          // 添加该邮箱对应的账户名
          names.put(a.get(i), a.get(0));
        }

        if (i > 1) {
          // 并查集的合并操作，合并一个账户中的所有邮箱
          q.put(find(q, a.get(i)), find(q, a.get(i - 1)));
        }
      }
    }

    // 暂时存储答案中的邮箱列表，每个键值对的键就是每个并查集集合的根元素
    Map<String, List<String>> temp = new HashMap<>();
    for (String email : q.keySet()) {
      // 获取当前邮箱对应并查集的根元素
      String root = find(q, email);
      // 将当前邮箱放入根元素对应的列表中
      if (!temp.containsKey(root)) {
        temp.put(root, new ArrayList<>());
      }
      temp.get(root).add(email);
    }

    // 将答案从映射中放到列表
    List<List<String>> res = new ArrayList<>();
    for (String root : temp.keySet()) {
      // 获取当前根元素对应的列表
      List<String> layer = temp.get(root);
      // 题目要求的排序
      Collections.sort(layer);
      // 添加姓名
      layer.add(0, names.get(root));
      // 将当前列表加入答案
      res.add(layer);
    }

    return res;
  }

  private static String find(Map<String, String> q, String x) {
    // 判断x是不是就是一个根元素
    if (!q.get(x).equals(x)) {
      // x不是根，那就通过递归find函数来找到x映射的元素的根元素（寻根）
      // 找到根元素之后，通过put方法将x直接映射到根元素，这样就免去中间的多次递归（归祖）
      q.put(x, find(q, q.get(x)));
    }

    // 最终，x映射的元素就是x所在的集合的根元素，返回x的根元素
    return q.get(x);
  }

  public static void main(String[] args) {
    List<String> account1 = new ArrayList<>();
    account1.add("John");
    account1.add("johnsmith@mail.com");
    account1.add("john00@mail.com");

    List<String> account2 = new ArrayList<>();
    account2.add("John");
    account2.add("johnnybravo@mail.com");

    List<String> account3 = new ArrayList<>();
    account3.add("John");
    account3.add("johnsmith@mail.com");
    account3.add("john_newyork@mail.com");

    List<String> account4 = new ArrayList<>();
    account4.add("Mary");
    account4.add("mary@mail.com");

    List<List<String>> accounts = new ArrayList<>();
    accounts.add(account1);
    accounts.add(account2);
    accounts.add(account3);
    accounts.add(account4);

    List<List<String>> result = accountsMerge(accounts);
    System.out.println(result.toString());
  }
}
